package com.ljx.Daoyu;

/**
 * @author 李加喜
 * @Package com.ljx.Daoyu
 * @date 2021-11-08 21:50
 */
//飞地的数量
public class FeiDao {
    public static void main(String[] args) {

    }
    public int numEnclaves(int[][] grid) {
        int res=0;
        int m=grid.length,n=grid[0].length;
        for (int i=0;i<m;i++){
            dfs(grid,i,0);
            dfs(grid,i,n-1);
        }
        for (int j=0;j<n;j++){
            dfs(grid,0,j);
            dfs(grid,m-1,j);
        }
        // 计算剩余的陆地
        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                if (grid[i][j]==1){
                    res++;
                }
            }
        }
        return res;
    }
    void dfs(int[][] grid, int i, int j) {
        int m = grid.length, n = grid[0].length;
        if (i < 0 || j < 0 || i >= m || j >= n) {
            // 超出索引边界
            return;
        }
        if (grid[i][j] == '0') {
            // 已经是海水了
            return;
        }
        // 将 (i, j) 变成海水
        grid[i][j] = '0';
        // 淹没上下左右的陆地
        dfs(grid, i + 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i - 1, j);
        dfs(grid, i, j - 1);
    }
}
